class Node {
    data;
    left;
    right;
    count;
    constructor(data, left, right) {
        this.data = data;
        this.left = left;
        this.right = right;
        this.count = 1;
    }
    show() {
        return this.data;
    }
};

class BST {
    //根节点
    root = null;

    //插入number类型的数据
    insertNumber(insertData) {
        const insertNode = new Node(insertData, null, null);
        if (this.root === null) {
            this.root = insertNode;
        }
        else {
            let current = this.root;
            let parent;
            while (true) {
                parent = current;
                if (insertData === current.data) {
                    current.count++;
                    return;
                }
                else if (insertData <= current.data) {
                    current = current.left;
                    if (current === null) {
                        parent.left = insertNode;
                        break;
                    }
                }
                else {
                    current = current.right;
                    if (current === null) {
                        parent.right = insertNode;
                        break;
                    }
                }
            }
            current = insertNode;
        }
    };
    //插入string类型的数据
    insertString(insertData) {
        const insertNode = new Node(insertData, null, null);
        if (this.root === null) {
            this.root = insertNode;
        }
        else {
            let current = this.root;
            let parent;
            while (true) {
                parent = current;
                const charCodeSum_currentData = this.getCharCodeSum(current.data);
                const charCodeSum_insertData = this.getCharCodeSum(insertData);
                if (insertData === current.data) {
                    current.count++;
                    return;
                }
                else if (charCodeSum_insertData <= charCodeSum_currentData) {
                    current = current.left;
                    if (current === null) {
                        parent.left = insertNode;
                        break;
                    }
                }
                else {
                    current = current.right;
                    if (current === null) {
                        parent.right = insertNode;
                        break;
                    }
                }
            }
            current = insertNode;
        }
    };
    //计算charcode的工具函数
    getCharCodeSum(str) {
        let sum = 0;
        for (let i = 0; i < str.length; i++) {
            sum += str.charCodeAt();
        }
        return sum;
    };

    //获取最大最小值
    getMax() {
        let current = this.root;
        while (current.right !== null) {
            current = current.right;
        };
        return current.data;
    };
    getMin() {
        let current = this.root;
        while (current.left !== null) {
            current = current.left;
        };
        return current.data;
    };

    //中序遍历并附带个数
    inorder(node = this.root) {
        if (node !== null) {
            this.inorder(node.left);
            console.log(node.data + " - " + node.count);
            this.inorder(node.right);
        }
    };

    //查找节点
    find(findData) {
        let current = this.root;
        while (current !== null) {
            if (findData === current.data) {
                return current;
            }
            else if (findData > current.data) {
                current = current.right;
            }
            else {
                current = current.left;
            }
        }
        return null;
    };
    findLatestNode(node) {
        let current = node;
        while (current.right !== null) {
            current = current.right;
        }
        return current;
    }

    //移除节点
    remove(removeData) {
        if (this.find(removeData) !== null) {
            this.removeNode(this.root, removeData);
            return true;
        }
        else return false;
    };
    removeNode(node, removeData) {
        if (node === null) {
            return null;
        }
        if (node.data === removeData) {
            if (node.left === null && node.right === null) {
                return null;
            }
            if (node.left === null) {
                return node.right;
            }
            if (node.right === null) {
                return node.left;
            }
            if (node.left !== null && node.right !== null) {
                const templeNode = this.findLatestNode(node);
                node.data = templeNode.data;
                node.right = this.removeNode(node.right, templeNode.node);
            }
        }
        else if (removeData > node.data) {
            node.right = this.removeNode(node.right, removeData);
            return node;
        }
        else {
            node.left = this.removeNode(node.left, removeData);
            return node;
        }
    };

    //获取节点个数
    getNodeSum() {
        return this.caculateNodeSum(this.root);
    };
    caculateNodeSum(node) {
        if (node === null) {
            return 0;
        }
        else {
            return 1 + this.caculateNodeSum(node.right) + this.caculateNodeSum(node.left);
        }
    };

    //获取边的个数
    getEdgeSum() {
        return this.caculateEdgeSum(this.root);
    };
    caculateEdgeSum(node) {
        if (node.left === null && node.right === null) {
            return 0;
        }
        else if (node.left === null) {
            return 1 + this.caculateEdgeSum(node.right);
        }
        else if (node.right === null) {
            return 1 + this.caculateEdgeSum(node.left);
        }
        else {
            return 2 + this.caculateEdgeSum(node.right) + this.caculateEdgeSum(node.left);
        }
    }
}

const tree = new BST();

const arr = [20, 10, 30, 5, 15, 25, 40, 3, 7, 12, 17, 45, 13];
arr.forEach((item) => {
    tree.insertNumber(item);
})

// console.log(tree.getMax());
// console.log(tree.getMin());
// tree.inorder();
// console.log(tree.find(1));
// tree.remove(1);
// tree.inorder();

// console.log(tree.getNodeSum());
// console.log(tree.getEdgeSum());

const text = `One morning a fox sees a cock.He think,"This is my breakfast.''
He comes up to the cock and says,"I know you can sing very well.Can you sing for me?''The cock is glad.He closes his eyes and begins to sing.
he fox sees that and caches him in his mouth and carries him away. The people in the field see the fox.
They cry,"Look,look!The fox is carrying the cock away.''The cock says to the fox,"Mr Fox,do you understand?The people say you are carrying their cock away.Tell them it is yours.Not theirs.''
The fox opens his mouth ang says,"The cock is mine,not yours.''Just then the cock runs away from the fox and flies into the tree.`;

const textArray = text.replace(/[\r\n]/g, "").split(" ");
textArray.forEach((item) => {
    tree.insertString(item);
})

tree.inorder();